package com.tgy.algorithm.base._排序;

import java.util.Arrays;

public class _找出最大的几个数 {

    public static void swap(int[] nums,int i,int j) {
        int tmp = nums[i];
        nums[i] =  nums[j];
        nums[j] = tmp;
    }

    public static void heapInsert(int[] nums,int index) {
        if (nums == null
                || nums.length <= 1
                || index <= 0
                || index >= nums.length) {
            return;
        }

        /**
         *         0
         *       1    2
         *     3   4 5  6
         */

        // (3 - 1) / 2
        int parentIndex =  (index - 1) / 2;
        // 当index == 0 的时候，parentIndex也是0，则这个时候while条件为false，退出循环
        while (nums[index] < nums[parentIndex]) {
            swap(nums, index, parentIndex);
            index = parentIndex;
            parentIndex = (index - 1) / 2;
        }
    }

    public static void heapify(int[] nums,int index) {

        if (nums == null || nums.length < 2) {
            return;
        }

        int length = nums.length;
        if (index < 0 || index >= length) {
            return;
        }

        swap(nums,  index, 0);
        /**
         *          0
         *       1      2
         *     3   4  5   6
         *     index 1 * 2 + 1
         */
        int i = 0;
        // 顶部往底部走
        while (true) {
            int leftIndex = (i << 1) + 1;
            if (leftIndex >= index) {
                break;
            }
            int maxIndex =  leftIndex + 1 >= index ? leftIndex:(nums[leftIndex] < nums[leftIndex + 1] ? leftIndex:
                    leftIndex + 1);
            if (nums[maxIndex] > nums[i]) {
                break;
            }
            swap(nums, i, maxIndex);
            i = maxIndex;
        }
    }

    public static int[] findMaxNums(int[] nums, int k) {

        if (k <= 0) {
            return null;
        }

        int[] maxNums = new int[k];
        int len = 0;
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            if (len < k) {
                maxNums[len++] = nums[i];
                // 维护一个最小堆
                heapInsert(maxNums, len - 1);
            }else {
                if (nums[i] > maxNums[0]) {
                    maxNums[0] = nums[i];
                    heapify(maxNums, k - 1);
                }
            }
        }

        return maxNums;
    }

    public static void main(String[] args) {
        int[] maxNums = findMaxNums(new int[]{3, 2,20 ,1, 5, 6, 4}, 4);
        System.out.println(Arrays.toString(maxNums));
    }
}
